from RandomList import GetRandomList

def merge(arr, start, mid, end):
	start2 = mid + 1
	if (arr[mid] <= arr[start2]):
		return
    # 其实就是partition之后把后面一半中大的数往前挤
	while (start <= mid and start2 <= end):
		if (arr[start] <= arr[start2]):
			start += 1
		else:
			value = arr[start2]
			index = start2
			while (index != start):
				arr[index] = arr[index - 1]
				index -= 1

			arr[start] = value
			start += 1
			mid += 1
			start2 += 1

def merge_sort_inplace(arr, l, r):
	if (l < r):
		m = l + (r - l) // 2
		merge_sort_inplace(arr, l, m)
		merge_sort_inplace(arr, m + 1, r)
		merge(arr, l, m, r)







if __name__ == "__main__":
    
    Arr = GetRandomList(1000)
    merge_sort_inplace(Arr, 0, len(Arr) - 1)
    print(Arr)